{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Ideal Subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestIdealString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长理想子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由小写字母组成的字符串 <code>s</code> ，和一个整数 <code>k</code> 。如果满足下述条件，则可以将字符串 <code>t</code> 视作是 <strong>理想字符串</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>t</code> 是字符串 <code>s</code> 的一个子序列。</li>\n",
    "\t<li><code>t</code> 中每两个 <strong>相邻</strong> 字母在字母表中位次的绝对差值小于或等于 <code>k</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回 <strong>最长</strong> 理想字符串的长度。</p>\n",
    "\n",
    "<p>字符串的子序列同样是一个字符串，并且子序列还满足：可以经由其他字符串删除某些字符（也可以不删除）但不改变剩余字符的顺序得到。</p>\n",
    "\n",
    "<p><strong>注意：</strong>字母表顺序不会循环。例如，<code>'a'</code> 和 <code>'z'</code> 在字母表中位次的绝对差值是 <code>25</code> ，而不是 <code>1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"acfgbd\", k = 2\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>最长理想字符串是 \"acbd\" 。该字符串长度为 4 ，所以返回 4 。\n",
    "注意 \"acfgbd\" 不是理想字符串，因为 'c' 和 'f' 的字母表位次差值为 3 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcd\", k = 3\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>最长理想字符串是 \"abcd\" ，该字符串长度为 4 ，所以返回 4 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 25</code></li>\n",
    "\t<li><code>s</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-ideal-subsequence](https://leetcode.cn/problems/longest-ideal-subsequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-ideal-subsequence](https://leetcode.cn/problems/longest-ideal-subsequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"acfgbd\"\\n2', '\"abcd\"\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s, k):\n",
    "        # if not s:\n",
    "        #     return 0\n",
    "        # dp = []\n",
    "        # # dp = [[0] * (len(s)) for _ in range(len(s))]\n",
    "        # # dp.append(1)\n",
    "        # # flag = s[0]\n",
    "        # for i in range(0,len(s)):\n",
    "        #     flag = s[i]\n",
    "        #     # print(flag)\n",
    "        #     # dp.append(1)\n",
    "        #     max_num = 1\n",
    "        #     for j in range(i+1,len(s)):\n",
    "        #         print(flag)\n",
    "        #         if abs(ord(s[j])-ord(flag))<=k:\n",
    "        #             max_num += 1\n",
    "        #             flag = s[j]\n",
    "        #         if j == len(s)-1:\n",
    "        #             dp.append(max_num)\n",
    "        #     exit()\n",
    "        #     # print(dp)\n",
    "        # return max(dp)\n",
    "        f = [0] * 26\n",
    "        for c in s:\n",
    "            # print(c)\n",
    "            c = ord(c) - ord('a')\n",
    "            # print(c)\n",
    "            # print(max(c - k, 0))\n",
    "            # print(c + k + 1)\n",
    "            # print(f[max(c - k, 0): c + k + 1])\n",
    "            # print(f)\n",
    "            f[c] = 1 + max(f[max(c - k, 0): c + k + 1])\n",
    "        # print(f)\n",
    "        return max(f)\n",
    "\n",
    "\n",
    "# a = Solution()\n",
    "# s = \"eduktdb\"\n",
    "# k = 15\n",
    "# print(a.longestIdealString(s,k))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        dp = [0] * 26\n",
    "        maxlen = 1\n",
    "        for c in s:\n",
    "            res = ord(c) - ord('a')\n",
    "            dp[res] = 1 + max(dp[max(res - k, 0): res + k + 1])\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        f = [0] * 26\n",
    "        for c in s:\n",
    "            c = ord(c) - ord('a')\n",
    "            f[c] = 1 + max(f[max(c - k, 0): c + k + 1])\n",
    "        return max(f)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        dp = [0] * 26\n",
    "        for i in s:\n",
    "            per = ord(i) - ord('a')\n",
    "            dp[per] = 1 + max(dp[max(per - k,0):per + k + 1])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        f = [0] * 26\n",
    "        for c in s:\n",
    "            c = ord(c) - ord('a')\n",
    "            f[c] = 1 + max(f[max(c - k, 0): c + k + 1])\n",
    "        return max(f) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        f=[0]*26\n",
    "        for c in s:\n",
    "            c=ord(c)-ord('a')\n",
    "            f[c]=max(f[max(c-k,0):c+k+1])+1\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        f = [0] * 26\n",
    "        for c in s:\n",
    "            c = ord(c) - ord('a')\n",
    "            f[c] = 1 + max(f[max(c - k, 0): c + k + 1])\n",
    "        return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        dp = [0] * 26\n",
    "        ans = 1\n",
    "        for i in range(len(s)):\n",
    "            idx = ord(s[i]) - 97\n",
    "\n",
    "            tmp = 1\n",
    "            for j in range(max(idx - k, 0), min(idx + k, 25) + 1):\n",
    "                tmp = max(tmp, dp[j] + 1)\n",
    "\n",
    "            dp[idx] = tmp\n",
    "\n",
    "            ans = max(ans, dp[idx])\n",
    "        \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        f = [0] * 26\n",
    "        for c in s:\n",
    "            c = ord(c) - ord('a')\n",
    "            f[c] = 1 + max(f[max(c - k, 0): c + k + 1])\n",
    "        return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        tail_dic = collections.defaultdict(int)\n",
    "        for i in s:\n",
    "            tail_dic[i] = 1 + max( [tail_dic[ chr( ord(i) + j) ] for j in range(-k,k+1) ] )\n",
    "        return max(tail_dic.values())        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        # @cache\n",
    "        # def dfs(i):\n",
    "        #     res = 1\n",
    "        #     for j in range(i+1, n):\n",
    "        #         if abs(ord(s[j]) - ord(s[i])) <= k:\n",
    "        #             res = max(res, dfs(j)+1)\n",
    "        #     return res\n",
    "        # return dfs(0)\n",
    "\n",
    "        # f[i][c] 表示前 i 个子福利吗选一个末尾字符为 c 的李想字符串的最长长度\n",
    "        # 选s[i]: f[i][c] = max(f[i-1][j] +1 [c-k, c+k] [0, 25])\n",
    "        # 压缩第一维\n",
    "        f = [0] * 26\n",
    "        for c in s:\n",
    "            c = ord(c) - ord('a')\n",
    "            f[c] = max(f[max(c-k, 0):c+k+1]) + 1\n",
    "        return max(f)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        def order(ch):\n",
    "            return ord(ch)-ord(\"a\")\n",
    "        n=len(s)\n",
    "        d=collections.defaultdict(int)\n",
    "        #dp=[1]*n\n",
    "        d[order(s[0])]=1\n",
    "        for i in range(1,n):\n",
    "            o=order(s[i])\n",
    "            tp=1\n",
    "            for j in range(max(0,o-k),min(26,o+k+1)):\n",
    "                if j in d:\n",
    "                    tp=max(tp,d[j]+1)\n",
    "            d[o]=tp\n",
    "        ans=0\n",
    "        for key in d:\n",
    "            if d[key]>ans:\n",
    "                ans=d[key]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        # 数据量不支持O(n^2)的算法（最长递增子序列的思路不能用）\n",
    "        # dp[i]：以ASCII码为i结尾的最长理想子序列长度\n",
    "        dp=[0]*26\n",
    "        shift=ord('a')\n",
    "        for i in s:\n",
    "            left=max(ord(i)-k,ord('a'))-shift\n",
    "            right=min(ord(i)+k,ord('z'))-shift\n",
    "            dp[ord(i)-shift]=max(dp[left:right+1])+1\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        dp = [0 for _ in range(26)]\n",
    "\n",
    "        for w in s:\n",
    "            idx = ord(w) - ord('a')\n",
    "            dp[idx] =\\\n",
    "                max(dp[max(0, idx - k) :idx + k + 1]) + 1\n",
    "\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        dp = [0] * 26\n",
    "        for c in s:\n",
    "            num = ord(c) - ord(\"a\")\n",
    "            dp[num] = max(dp[max(num-k,0):min(num+k+1, 26)]) + 1\n",
    "        return max(dp)\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        f = [0] * 26\n",
    "        for c in s:\n",
    "            c = ord(c) - ord('a')\n",
    "            f[c] = 1 + max(f[max(c - k, 0): c + k + 1])\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        f = [0] * 26\n",
    "        for c in s:\n",
    "            c = ord(c) - ord('a')\n",
    "            f[c] = 1 + max(f[max(c - k, 0): c + k + 1])\n",
    "        return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        arr=[0]*26\n",
    "        for ch in s:\n",
    "            idx=ord(ch)-ord('a')\n",
    "            cur=0\n",
    "            for j in range(max(0,idx-k),min(26,idx+k+1)):\n",
    "                cur=max(cur,arr[j])\n",
    "            arr[idx]=cur+1\n",
    "        return max(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        longests = [0]*26\n",
    "        ordA = ord('a')\n",
    "        for c in s:\n",
    "            c = ord(c) - ordA\n",
    "            l, r = max(0, c - k), min(25, c + k)\n",
    "            longests[c] = max(longests[l:r+1]) + 1\n",
    "        return max(longests)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        f, g = [0 for _ in range(26)], [0 for _ in range(26)]\n",
    "        for c in s:\n",
    "            for j in range(26):\n",
    "                g[j] = max(f[j], 0 if abs(j - ord(c) + ord('a')) > k else f[ord(c) - ord('a')] + 1)\n",
    "            f = g[:]\n",
    "        return max(g)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        f = [0] * 26\n",
    "        for c in s:\n",
    "            idx = ord(c) - ord('a')\n",
    "            left = max(idx - k, 0)\n",
    "            right = min(idx + k, 25)\n",
    "            f[idx] = 1 + max(f[left : right + 1])\n",
    "\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        #dp[j]表示以s[j]结尾的最长子序列\n",
    "        #dp[j] = 1 如果前面所有s【i】与s【j】差都大于等于K\n",
    "        #dp[j]  =  max(集合：与s[j]差小于等于K的字母的dp) + 1\n",
    "\n",
    "        f = [0 for i in range(26)]\n",
    "        for ch in s:\n",
    "            shu = ord(ch) - ord('a')\n",
    "            f[shu] = 1 + max(f[max(shu-k,0):shu+k+1])\n",
    "        return max(f)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0]*26\n",
    "        for v in s:\n",
    "            c = ord(v) - ord('a')\n",
    "            dp[c] = 1 + max(dp[max(c-k,0):c+k+1])\n",
    "        # print(dp)\n",
    "        return max(dp)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        # 动态规划 + 状态压缩\n",
    "        # dp[i][j]表示从0-i的字符串中选则一个以j结尾的理想字符串的最长长度\n",
    "        # 选第i个字符 dp[i][j] = max(dp[i-1][j'])+1,j'与j的差值绝对差值小于或等于k \n",
    "        # 不选第i个字符 dp[i][j] = dp[i-1][j]\n",
    "        f = [0]*26\n",
    "        for c in s:\n",
    "            c = ord(c)-ord('a')\n",
    "            f[c] = max(f[max(c-k,0):c+k+1])+1\n",
    "        return max(f)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        \n",
    "\n",
    "        dp=[0]*26\n",
    "        for c in s:\n",
    "            c=ord(c)-ord('a')\n",
    "            dp[c]=1+max(dp[max(c-k,0):c+k+1])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        #f[i][c]f[i][c]f[i][c] 表示 sss 的前 iii 个字母中的以 ccc 结尾的理想字符串的最长长度。\n",
    "        f=[0]*26\n",
    "        for c in s:\n",
    "            c=ord(c)-ord('a')\n",
    "            f[c]=max(f[max(c-k,0):c+k+1])+1\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        dp=[0]*26\n",
    "        for i in range(n):\n",
    "            c=ord(s[i])-ord('a')\n",
    "            for j in range(max(0,c-k),min(c+k+1,26)):\n",
    "                dp[c]=max(dp[j],dp[c])\n",
    "            dp[c]+=1\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        f = [0] * 26\n",
    "\n",
    "        for ch in s:\n",
    "            idx = ord(ch) - ord('a')\n",
    "            minidx = max(idx - k, 0)\n",
    "            maxidx = min(idx + k, 25)\n",
    "            f[idx] = 1 + max(f[minidx : maxidx + 1])\n",
    "        \n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        f = [0]*26\n",
    "        for c in s:\n",
    "            c = ord(c) - ord('a')\n",
    "            f[c] = max(f[max(c-k,0):c+k+1]) + 1\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        dp = [0 for _ in range(26)]\n",
    "\n",
    "        for w in s:\n",
    "            idx = ord(w) - ord('a')\n",
    "            # dp数组里的每个数字一定是尾部数字\n",
    "            # 绝对值差小于k包括自己\n",
    "            dp[idx] =\\\n",
    "                max(dp[max(0, idx - k) :idx + k + 1]) + 1\n",
    "\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        dp=[0]*26\n",
    "        ans=0\n",
    "\n",
    "        for i in range(n):\n",
    "            idx=ord(s[i])-ord('a')\n",
    "            left=max(idx-k,0)\n",
    "            right=min(idx+k,25)\n",
    "            cur=0\n",
    "\n",
    "            for j in range(left,right+1):\n",
    "\n",
    "                cur=max(cur,dp[j]+1)\n",
    "            \n",
    "            dp[idx]=cur\n",
    "            ans=max(ans,cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        my_mat=[0]*26\n",
    "        for i in s:\n",
    "            index1=ord(i)-ord('a')\n",
    "            starti=max(0,index1-k)\n",
    "            endi=min(index1+k,25)\n",
    "            temp=1\n",
    "            for j in range(starti,endi+1):\n",
    "                temp=max(temp,1+my_mat[j])\n",
    "\n",
    "            my_mat[index1]=temp\n",
    "\n",
    "        return max(my_mat)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        # 记录以每个字符结尾的最长序列长度，减少前向搜索次数\n",
    "        dp = [0] * 26\n",
    "        for c in s:\n",
    "            i = ord(c) - ord('a')  # 当前字符的序号\n",
    "            start_c = i - k if i-k >=0 else 0\n",
    "            end_c = i + k + 1 if i+k+1 <=25 else 26\n",
    "            dp[i] = max(dp[start_c: end_c]) + 1\n",
    "        return max(dp)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        \n",
    "        f = [0] * 26\n",
    "\n",
    "        for c in s:\n",
    "            left = max(ord(c) - ord('a') - k, 0)\n",
    "            right = min(ord(c) - ord('a') + k + 1, 26)\n",
    "\n",
    "            cnt = max(f[left:right])\n",
    "\n",
    "            f[ord(c) - ord('a')] = cnt + 1\n",
    "        \n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ALPHABET = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        last = defaultdict(int)\n",
    "        nbs = defaultdict(set)\n",
    "        for c1 in ALPHABET:\n",
    "            for c2 in ALPHABET:\n",
    "                if abs(ord(c1) - ord(c2)) <= k:\n",
    "                    nbs[c1].add(c2)\n",
    "\n",
    "        for c1 in s:\n",
    "            last[c1] = max(last[c2] for c2 in nbs[c1]) + 1\n",
    "        \n",
    "        return max(last.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        \n",
    "        f = [0] * 26\n",
    "\n",
    "        for c in s:\n",
    "            c = ord(c) - ord('a')\n",
    "            f[c] = 1 + max(f[max(c-k, 0):c+k+1])\n",
    "\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [ 0 ] * 26\n",
    "\n",
    "        for i in range(n):\n",
    "            idx = ord(s[i])- ord('a')\n",
    "            dp[idx] = max(dp[max(0, idx - k):min(25, idx+k)+1]) + 1\n",
    "\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        pre = [0]*26\n",
    "        dct = [[] for _ in range(26)]\n",
    "        for i in range(26):\n",
    "            for j in range(26):\n",
    "                if abs(i-j) <= k:\n",
    "                    dct[i].append(j)\n",
    "        for w in s:\n",
    "            i = ord(w) - ord(\"a\")\n",
    "            cur = 1\n",
    "            for j in dct[i]:\n",
    "                if pre[j]+1>cur:\n",
    "                    cur = pre[j]+1\n",
    "            pre[i] = cur\n",
    "        return max(pre)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        y=defaultdict(int)\n",
    "        for i in range (0,n):\n",
    "            u=s[i]\n",
    "            p=[chr(j) for j in range (ord(u)-k,ord(u)+k+1)]\n",
    "            y[u]=1+max([y[j] for j in p])\n",
    "        return max([y[u] for u in y])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        # dp[i][j]表示0-i的字符串以j结尾的最长理想字符串的长度\n",
    "        # 不选第i个字符串\n",
    "        # dp[i][j] = dp[i-1][j]\n",
    "        # 选第i个字符串\n",
    "        # dp[i][j] = dp[][j']\n",
    "        dp = [0]*(26)\n",
    "        for c in s:\n",
    "            c = ord(c)-ord('a')\n",
    "            dp[c] = max(dp[max(0,c-k):c+k+1])+1\n",
    "        return max(dp) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        f = [0] * 26\n",
    "        for c in s:\n",
    "            c = ord(c) - ord('a')\n",
    "            f[c] = 1 + max(f[max(c - k, 0): c + k + 1])\n",
    "        return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0] * 26\n",
    "        for c in s:\n",
    "            c = ord(c) - ord('a')\n",
    "            dp[c] = 1 + max(dp[max(c - k, 0): c + k + 1])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        orda = ord('a')\n",
    "        count = [0] * 26\n",
    "        for c in s:\n",
    "            x = ord(c) - orda\n",
    "            count[x] = max(count[j] for j in range(max(x - k, 0), min(x + k + 1, 26))) + 1\n",
    "        return max(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        f = [0] * 26\n",
    "        for c in s:\n",
    "            c = ord(c) - ord('a')\n",
    "            f[c] = 1 + max(f[max(c - k, 0): c + k + 1])\n",
    "        return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        dp = [0]*26\n",
    "        for c in s:\n",
    "            Id = ord(c)-97\n",
    "            dp[Id] = 1+max(dp[max(0, Id-k):Id+k+1])\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        dic = [-1]*26\n",
    "        n = len(s)\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            Id = ord(s[i])-97\n",
    "            start = max(0, Id-k)\n",
    "            end = min(25, Id+k)\n",
    "            #print(Id, dic, dp, start, end)\n",
    "            for j in range(start, end+1):\n",
    "                dp[i] = max(dp[i], dp[dic[j]])\n",
    "            dp[i] += 1\n",
    "            dic[Id] = i\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "        \n",
    "        def GetId(c):\n",
    "            return ord(c)-97\n",
    "\n",
    "        dic = [-1]*26\n",
    "        n = len(s)\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            Id = GetId(s[i])\n",
    "            start = max(0, Id-k)\n",
    "            end = min(25, Id+k)\n",
    "            #print(Id, dic, dp, start, end)\n",
    "            for j in range(start, end+1):\n",
    "                dp[i] = max(dp[i], dp[dic[j]])\n",
    "            dp[i] += 1\n",
    "            dic[Id] = i\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "\n",
    "        # mp = collections.defaultdict(int)\n",
    "        mp = {}\n",
    "        dp = [1] * len(s)\n",
    "        mp[ord(s[0])] = 1\n",
    "        ans = 1\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            idx = ord(s[i])\n",
    "            lower = max(97, idx - k)\n",
    "            upper = min(122,idx + k)\n",
    "\n",
    "            for j in range(lower, upper + 1):\n",
    "                if j in mp:\n",
    "                    dp[i] = max(dp[i], mp[j] + 1)\n",
    "\n",
    "\n",
    "            if idx not in mp:\n",
    "                mp[idx] = dp[i]\n",
    "            else:\n",
    "                mp[idx] = max(mp[idx], dp[i])\n",
    "\n",
    "            ans = max(ans, dp[i])\n",
    "        \n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        dp=[0]*n\n",
    "        lastindex=[-1]*26\n",
    "        for i in range(n):\n",
    "            for j in range(26):\n",
    "                if abs(ord(s[i])-ord('a')-j)<=k:\n",
    "                    dp[i]=max(dp[i],(dp[lastindex[j]] if lastindex[j]!=-1 else 0)+1)\n",
    "\n",
    "            lastindex[ord(s[i])-ord('a')]=i\n",
    "\n",
    "\n",
    "\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        dp = [1] * n\n",
    "\n",
    "        dt = [-1] * 26\n",
    "        for i in range(n):\n",
    "            dpos = ord(s[i]) - ord('a')\n",
    "            for j in range(dpos - k, dpos + k+1):\n",
    "                if j < 0 or j>= 26:\n",
    "                    continue\n",
    "                if dt[j] != -1:\n",
    "                    dp[i] = max(dp[i], 1 + dp[dt[j]])\n",
    "            dt[dpos] = i\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        def char2int(c):\n",
    "            return ord(c) - 97\n",
    "        n = len(s)\n",
    "        dp = [0]*n\n",
    "        d = [-1]*26\n",
    "        for i,c in enumerate(s):\n",
    "            ci = char2int(c)\n",
    "            dp[i] = 1\n",
    "            for j in range(max(0,ci-k), min(26,ci + k + 1)):\n",
    "                if d[j] != -1 and dp[d[j]]+1>dp[i]:\n",
    "                    dp[i] = dp[d[j]]+1\n",
    "            d[ci] = i\n",
    "            # print(dp)\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        dic = [-1]*26\n",
    "        n = len(s)\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            Id = ord(s[i])-97\n",
    "            start = max(0, Id-k)\n",
    "            end = min(25, Id+k)\n",
    "            #print(Id, dic, dp, start, end)\n",
    "            for j in range(start, end+1):\n",
    "                dp[i] = max(dp[i], dp[dic[j]])\n",
    "            dp[i] += 1\n",
    "            dic[Id] = i\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "        \n",
    "        def GetId(c):\n",
    "            return ord(c)-97\n",
    "\n",
    "        dic = [-1]*26\n",
    "        n = len(s)\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            Id = GetId(s[i])\n",
    "            start = max(0, Id-k)\n",
    "            end = min(25, Id+k)\n",
    "            #print(Id, dic, dp, start, end)\n",
    "            for j in range(start, end+1):\n",
    "                dp[i] = max(dp[i], dp[dic[j]])\n",
    "            dp[i] += 1\n",
    "            dic[Id] = i\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        def GetId(c):\n",
    "            return ord(c)-97\n",
    "\n",
    "        dic = [-1]*26\n",
    "        n = len(s)\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            Id = GetId(s[i])\n",
    "            start = max(0, Id-k)\n",
    "            end = min(25, Id+k)\n",
    "            #print(Id, dic, dp, start, end)\n",
    "            for j in range(start, end+1):\n",
    "                dp[i] = max(dp[i], dp[dic[j]])\n",
    "            dp[i] += 1\n",
    "            dic[Id] = i\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        def GetId(c):\n",
    "            return ord(c)-97\n",
    "\n",
    "        dic = [-1]*26\n",
    "        n = len(s)\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            Id = GetId(s[i])\n",
    "            start = max(0, Id-k)\n",
    "            end = min(25, Id+k)\n",
    "            #print(Id, dic, dp, start, end)\n",
    "            for j in range(start, end+1):\n",
    "                dp[i] = max(dp[i], dp[dic[j]])\n",
    "            dp[i] += 1\n",
    "            dic[Id] = i\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * 26 for _ in range(n)]\n",
    "        for i in range(26):\n",
    "            dp[0][i] = int(ord(s[0]) - ord('a') == i)\n",
    "        for i in range(1, n):\n",
    "            c = ord(s[i]) - ord('a')\n",
    "            for j in range(26):\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "\n",
    "            for cp in range(26):\n",
    "                if abs(c - cp) <= k:\n",
    "                    dp[i][c] = max(dp[i][c], dp[i-1][cp]+1)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(26):\n",
    "                ans = max(ans, dp[i][j])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        f = [[0] * 26 for _ in range(n + 1)]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            p = abs(ord(s[i]) - ord('a'))\n",
    "\n",
    "            # 不选\n",
    "            for j in range(26):\n",
    "                f[i + 1][j] = f[i][j]\n",
    "\n",
    "            # 选了\n",
    "            for j in range(max(0, p - k), min(26, p + k + 1), 1):\n",
    "                f[i + 1][p] = max(f[i + 1][p], f[i][j] + 1) \n",
    "        return max(f[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        dp=[[0 for i in range(26)] for i in range(len(s))]\n",
    "        dp[0][ord(s[0])-97]=1\n",
    "        for i in range(1,len(s)):\n",
    "            for j in range(26):\n",
    "                c=ord(s[i])-ord(\"a\")\n",
    "                if c==j:\n",
    "                    #讨论选或者不选,直接取最大值\n",
    "                    for t in range(26):\n",
    "                        #这个可以改为非循环的，所以不要if还else了，dp[i][c]与循环无关啊，循环只是找到满足特定要求的前一刻状态\n",
    "                        if abs(t-c)<=k:\n",
    "                            dp[i][c]=max(dp[i-1][c],dp[i][c],dp[i-1][t]+1)\n",
    "                else:\n",
    "                    dp[i][j]=dp[i-1][j]\n",
    "        return max(dp[-1])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        #Review this\n",
    "        #dp子序列问题\n",
    "        #dp[i][j]定义为s前i序号子字符串中选出以j字符结尾的最长理想字符串长度，定义这个j是方便转移的，因为\n",
    "        #这个题是相邻字符的问题\n",
    "        #转移方法为dp[i][c]=(选或者不选，当然如果是遍历dp表，那就要都遍历，如果无法选那就直接继承)\n",
    "        #dp[i][j]=dp[i-1][j]#没法选s[i]，dp[i][j]=max(dp[i-1][j],max(dp[i-1][abs(j-t)<=k])+1的这段)\n",
    "        dp=[[0 for i in range(26)] for i in range(len(s))]\n",
    "        #初始化\n",
    "        dp[0][ord(s[0])-ord(\"a\")]=1\n",
    "        for i in range(1,len(s)):\n",
    "            c=ord(s[i])-97\n",
    "            for j in range(26):\n",
    "                #如果刚好这个j是s[i]那就可以选，否则不能选\n",
    "                if c==j:\n",
    "                    dp[i][j]=max(dp[i-1][j],max(dp[i-1][max(0,c-k):c+k+1])+1)\n",
    "                else:\n",
    "                    dp[i][j]=dp[i-1][j]\n",
    "        return max(dp[-1])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        dp=[[0 for _ in range(26)]for _ in range(len(s))]\n",
    "        dp[0][ord(s[0])-ord('a')]=1\n",
    "        for i in range(1,len(s)):\n",
    "            for j in range(26):\n",
    "                dp[i][j]=dp[i-1][j]\n",
    "            for x in range(k+1):\n",
    "                if ord(s[i])-ord('a')-x>=0:\n",
    "                    dp[i][ord(s[i])-ord('a')]=max(dp[i][ord(s[i])-ord('a')],dp[i-1][ord(s[i])-ord('a')-x]+1)\n",
    "                if ord(s[i])-ord('a')+x<26:\n",
    "                    dp[i][ord(s[i])-ord('a')]=max(dp[i][ord(s[i])-ord('a')],dp[i-1][ord(s[i])-ord('a')+x]+1)\n",
    "        return max(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        dp=[[0 for i in range(26)] for i in range(len(s))]\n",
    "        dp[0][ord(s[0])-97]=1\n",
    "        for i in range(1,len(s)):\n",
    "            for j in range(26):\n",
    "                c=ord(s[i])-ord(\"a\")\n",
    "                if c==j:\n",
    "                    #讨论选或者不选,直接取最大值,python区间是左闭右开区间\n",
    "                        dp[i][c]=max(dp[i-1][c],dp[i][c],max(dp[i-1][max(c-k,0):c+k+1])+1)\n",
    "                else:\n",
    "                    dp[i][j]=dp[i-1][j]\n",
    "        return max(dp[-1])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIdealString(self, s: str, k: int) -> int:\n",
    "        dp=[[0 for i in range(26)] for i in range(len(s))]\n",
    "        dp[0][ord(s[0])-97]=1\n",
    "        for i in range(1,len(s)):\n",
    "            for j in range(26):\n",
    "                c=ord(s[i])-ord(\"a\")\n",
    "                if c==j:\n",
    "                    #讨论选或者不选\n",
    "                    for t in range(26):\n",
    "                        if abs(t-c)<=k:\n",
    "                            dp[i][c]=max(dp[i-1][c],dp[i][c],dp[i-1][t]+1)\n",
    "                else:\n",
    "                    dp[i][j]=dp[i-1][j]\n",
    "        return max(dp[-1])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
